NOIP2012 普及组
T1:质因数分解
题目描述
已知正整数是两个不同的质数的乘积，试求出两者中较大的那个质数。
输入格式
一个正整数。
输出格式
一个正整数，即较大的那个质数。
输入输出样例
输入样例 #1
21
输出样例 #1
7
说明/提示
NOIP 2012 普及组 第一题
题解：
读入一个数字 之后，为了减少时间复杂度，首先将 开一下根，然后从 开始枚举 的质因数。唯一分解定理告诉我们，一个数只能分解为一组质数的乘积，所以，我们从从 到 来开始枚举 的质因数，如果发现 之后，便得到了一个较小的质因数 。为了得到较大的那一个，输出 就可以了。
#include <cmath>
#include <cstdio>
using namespace std;
int main() {
long long n;
scanf("%lld", &n);
int l = sqrt(n) + 1;
for (long long i = 2; i <= l; i++)
if (n % i == 0) {
printf("%lld\n", n / i);
return 0;
}
return 0;
}
T2:寻宝
题目描述
传说很遥远的藏宝楼顶层藏着诱人的宝藏。小明历尽千辛万苦终于找到传说中的这个藏宝楼，藏宝楼的门口竖着一个木板，上面写有几个大字：寻宝说明书。说明书的内容如下：
藏宝楼共有层，最上面一层是顶层，顶层有一个房间里面藏着宝藏。除了顶层外，藏宝楼另有层，每层个房间，这个房间围成一圈并按逆时针方向依次编号为。其中一些房间有通往上一层的楼梯，每层楼的楼梯设计可能不同。每个房间里有一个指示牌，指示牌上有一个数字，表示从这个房间开始按逆时针方向选择第个有楼梯的房间（假定该房间的编号为k），从该房间上楼，上楼后到达上一层的号房间。比如当前房间的指示牌上写着，则按逆时针方向开始尝试，找到第个有楼梯的房间，从该房间上楼。如果当前房间本身就有楼梯通向上层，该房间作为第一个有楼梯的房间。
寻宝说明书的最后用红色大号字体写着：“寻宝须知：帮助你找到每层上楼房间的指示牌上的数字（即每层第一个进入的房间内指示牌上的数字）总和为打开宝箱的密钥”。 请帮助小明算出这个打开宝箱的密钥。
输入格式
第一行个整数和，之间用一个空格隔开。表示除了顶层外藏宝楼共层楼，表示除顶层外每层楼有个房间。
接下来行，每行两个整数，之间用一个空格隔开，每行描述一个房间内的情况，其中第行表示第层号房间的情况（；）。第一个整数表示该房间是否有楼梯通往上一层（表示没有，表示有），第二个整数表示指示牌上的数字。注意，从号房间的楼梯爬到上一层到达的房间一定也是号房间。
最后一行，一个整数，表示小明从藏宝楼底层的几号房间进入开始寻宝（注：房间编号从开始）。
输出格式
一个整数，表示打开宝箱的密钥，这个数可能会很大，请输出对取模的结果即可。
输入输出样例
输入样例 #1
2 3
1 2
0 3
1 4
0 1
1 5
1 2
1
输出样例 #1
5
说明/提示
【数据范围】
对于50%数据，有；
对于100%数据，有。
NOIP 2012 普及组 第二题
题解：
本题就是一道模拟题，但是题目条件比较多，比较考察读题能力。
由于指示牌上的数字可能会很大，需要围着本层楼跑好几圈才能够跑到能像上一层的房间，所以，我们设置一个 数组存储每层楼中有楼梯的房间的总数。然后，将指示牌上的数字 一下对应的 ，就可以保证在一圈之内找到通往上一层的入口。
#include <iostream>
#define MOD 20123
using namespace std;
int room[10001][101][4];
int Floor[100001];
int main() {
int n, m, start;
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 0; j < m; j++) {
cin >> room[i][j][1] >> room[i][j][2];
Floor[i] += room[i][j][1];
}
cin >> start;
int ans = 0; //记录答案
for (int i = 1; i <= n; i++) { //从第一层楼开始向上爬
ans = (ans + room[i][start][2]) % MOD; //记录答案
int cs = 0, q = start;
room[i][start][2] = (room[i][q][2] - 1) % Floor[i] + 1; //剪枝，保证一圈之内找到入口
while (cs < room[i][q][2]) {
cs += room[i][start][1];
if (cs == room[i][q][2])
break;
start++;
if (start == m)
start = 0;
}
}
cout << ans << endl;
return 0;
}
T3:摆花
题目描述
小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共盆。通过调查顾客的喜好，小明列出了顾客最喜欢的种花，从到标号。为了在门口展出更多种花，规定第种花不能超过盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。
试编程计算，一共有多少种不同的摆花方案。
输入格式
第一行包含两个正整数和，中间用一个空格隔开。
第二行有个整数，每两个整数之间用一个空格隔开，依次表示。
输出格式
一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对取模的结果。
输入输出样例
输入样例 #1
2 4
3 2
输出样例 #1
2
说明/提示
【数据范围】
对于20%数据，有；
对于50%数据，有；
对于100%数据，有。
NOIP 2012 普及组 第三题
题解：
本题是一个动态规划问题，但是，本题却不需要 或 函数，而是只需要简单地从上一个状态转移到当前状态。
我们设置一个 数组，用 来表示当摆上 盆花时有多少种不同的摆花方案。
然后，我们用 来枚举每盆花，用 来枚举摆的花的数量，用 来枚举上一个状态，便可以得到 的动态转移方程，最后，输出 就可以辣！
#include <iostream>
#define MOD 1000007
using namespace std;
int a[101], DP[101];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
DP[0] = 1;
for (int i = 1; i <= n; i++) //从第一盆花开始枚举
for (int j = m; j >= 0; j--)
for (int k = 1; k <= min(j, a[i]); k++)
DP[j] = (DP[j] + DP[j - k]) % MOD;
cout << DP[m] << endl;
return 0;
}
T4:文化之旅
题目描述
有一位使者要游历各国，他每到一个国家，都能学到一种文化，但他不愿意学习任何一种文化超过一次（即如果他学习了某种文化，则他就不能到达其他有这种文化的国家）。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同，有些文化会排斥外来文化（即如果他学习了某种文化，则他不能到达排斥这种文化的其他国家）。
现给定各个国家间的地理关系，各个国家的文化，每种文化对其他文化的看法，以及这位使者游历的起点和终点（在起点和终点也会学习当地的文化），国家间的道路距离，试求从起点到终点最少需走多少路。
输入格式
第一行为五个整数 ，每两个整数之间用一个空格隔开，依次代表国家个数（国家编号为到 ），文化种数（文化编号为到），道路的条数，以及起点和终点的编号（保证 不等于）；
第二行为个整数，每两个整数之间用一个空格隔开，其中第 个数，表示国家的文化为。
接下来的 行，每行个整数，每两个整数之间用一个空格隔开，记第 行的第 j 个数为， 表示文化 排斥外来文化（ 等于时表示排斥相同文化的外来人）， 表示不排斥（注意 排斥 并不保证一定也排斥）。
接下来的 行，每行三个整数 ，每两个整数之间用一个空格隔开，表示国家 与国家 有一条距离为的可双向通行的道路（保证不等于 ，两个国家之间可能有多条道路）。
输出格式
一个整数，表示使者从起点国家到达终点国家最少需要走的距离数（如果无解则输出）。
输入输出样例
输入样例 #1
2 2 1 1 2
1 2
0 1
1 0
1 2 10
输出样例 #1
-1
输入样例 #2
2 2 1 1 2
1 2
0 1
0 0
1 2 10
输出样例 #2
10
说明/提示
输入输出样例说明
由于到国家 必须要经过国家，而国家的文明却排斥国家 的文明，所以不可能到达国家 。
输入输出样例说明
路线为 ->
【数据范围】
对于 100%的数据，有
NOIP 2012 普及组 第四题
题解：
Emmm......由于本题被证明没有靠谱的多项式复杂度的做法，所以没有正解。那么。。。就怎么玄学怎么来呗！
我采用了 求最短路的方法。我们用 表示 国家到 国家的最短路，并将所有的 赋值为正无穷。读入每条路径，将双向通行的道路转为单向通行的道路：判断这条路所联通的两个国家 、 的文化是否互相排斥。如果 不排斥 的话则添加 的道路， 不排斥 的话则添加 的道路。至此，初始化完毕。
函数里面就是三重 循环。用变量 枚举从 途径 的路径。如果 之间有路的话，那么， 。最后，判断一下 是否小于正无穷，小于的话输出 ，否则输出 。
#include <cstring>
#include <iostream>
using namespace std;
int c[101];
int exclude[101][101];
int n, k, m, s, t;
int road[101][101];
int pass[101][101];
void Floyd () {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j)
for (int k = 1; k <= n; k++)
if (i != k && j != k)
road[i][j] = min(road[i][j], (road[i][k] + road[k][j]));
}
int main() {
memset(road, 0x3f3f3f, sizeof(road));
cin >> n >> k >> m >> s >> t;
for (int i = 1; i <= n; i++)
cin >> c[i];
if(c[s] == c[t]){
cout << -1;
return 0;
}
for (int i = 1; i <= k; i++)
for (int j = 1; j <= k; j++)
cin >> exclude[i][j];
for (int i = 1; i <= m; i++) {
int u, v, d;
cin >> u >> v >> d;
if (c[u] != c[v] && exclude[c[v]][c[u]] == 0) //两个国家文化不同且不互相排斥
road[u][v] = min(road[u][v], d); // road 表示从 u 到 v 的最小路，所以要先判断 v 文化是否排斥 u 文化，
if (c[u] != c[v] && exclude[c[u]][c[v]] == 0)
road[v][u] = min(road[v][u], d);
}
Floyd();
if (road[s][t] < 0x3f3f3f)
cout << road[s][t] << endl;
else
cout << -1 << endl;
return 0;
}